#include <string>
#include <map>
#include <iostream>

using namespace std;

/**
 * @brief 从 s 的 pos 位置开始，截取 len 长度的字符，构建统计表格。
 * 
 * @param s 
 * @param pos 
 * @param len 
 * @return map<char, int> 
 */
map<char, int> buildTable(string s, int pos, int len) {
  map<char, int> mapping;

  for (int i = pos; i < pos + len; ++i) {
    if (mapping.find(s[i]) != mapping.end()) {
      // 如果表格中已经有 s[i] 这个字符的记录了，就把这个记录数加 1.
      mapping[s[i]] += 1;
    }
    else {
      // 否则，就为 s[i] 新建一条记录。
      mapping.insert({s[i], 1});
    }
  }

  return mapping;
}

/**
 * @brief 检测 s2 中是否包含 s1 的某个排列
 * 
 * @param s1 
 * @param s2 
 * @return true 
 * @return false 
 */
bool checkInclusion(string s1, string s2) {
  // 对 s1 构建表格
  map<char, int> table1 = buildTable(s1, 0, s1.size());

  // 对 s2 来说
  // 第一个滑动窗口的范围是 0 到 s1.size() - 1
  // 第二个滑动窗口的范围是 1 到 1 + s1.size() - 1
  // 第三个滑动窗口的范围是 2 到 2 + s1.size() - 1
  // 以此类推 ...
  for (int i = 0; i < s2.size() - s1.size(); ++i) {
    map<char, int> tmp = buildTable(s2, i, s1.size());

    if (tmp == table1) {
      return true;
    }
  }

  return false;
}

int main(int argc, char const *argv[])
{
  /* code */
  string s1 {"abc"};
  string s2 {"aboadacdb"};
  string s3 {"aboacbcdb"};

  cout << checkInclusion(s1, s2) << endl; // false
  cout << checkInclusion(s1, s3) << endl; // true
  
  return 0;
}
